package Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree<T extends Comparable<? super T>> implements BinaryTTree<T> {

    private BinaryNode<T> root;
    private int i;

    public BinaryTree() {
        this.root = null;
    }

    public BinaryNode<T> getRoot() {
        return root;
    }

    public BinaryTree(T[] preList) {
        this.i = 0;
        this.root = create(preList);
    }

    public BinaryNode<T> create(T[] preList) {
        BinaryNode<T> p = null;
        if (i < preList.length) {
            T elem = preList[i++];
            if (elem == null) return null;
            p = new BinaryNode<>(elem);
            p.left = create(preList);
            p.right = create(preList);
        }
        return p;
    }

    //返回是否为空
    @Override
    public boolean isEmpty() {
        return this.root == null;
    }

    //插入一个结点
    @Override
    public void insert(T x) {
        if (x != null) {
            this.root = new BinaryNode<>(x, root, null);
        }
    }

    @Override
    public BinaryNode<T> insert(BinaryNode<T> p, boolean left, T x) {
        if (x == null || p == null) return null;
        if (left) {
            return p.left = new BinaryNode<>(x, p.left, null);
        } else return p.right = new BinaryNode<>(x, p.right, null);
    }

    @Override
    public void clear() {
        root = null;
    }

    @Override
    public void preorder() {
        preorder(this.root);
        System.out.println();
    }

    public void preorderTraverse(){
        Stack<BinaryNode<T>> stack = new Stack<>();
        BinaryNode<T> p = root;
        while (p != null||!stack.isEmpty()){
            if (p != null){
                System.out.print(p);
                stack.push(p);
                p = p.left;
            }else {
                p = stack.pop();
                p = p.right;
            }
        }
    }

    private void preorder(BinaryNode<T> p) {
        if (p != null) {
            System.out.print(p);
            preorder(p.left);
            preorder(p.right);
        }
    }

    //判断该树是否是一棵排序二叉树
    boolean isSorted() {
        return checkSorted(root);
    }

    static Integer checkNum=Integer.MIN_VALUE;

    boolean checkSorted(BinaryNode<T> p) {
        if (p == null)return true;
        boolean left = checkSorted(p.left);
        if (!left)return false;
        if ((Integer)p.data <= checkNum)return false;
        checkNum = (Integer) p.data;
        return checkSorted(p.right);
    }


    @Override
    public void inorder() {
        inorder(this.root);
    }

    private void inorder(BinaryNode<T> p) {
        if (p != null) {
            inorder(p.left);
            System.out.print(p);
            inorder(p.right);
        }
    }

    //后序遍历
    @Override
    public void postorder() {
        postorder(this.root);
    }

    private void postorder(BinaryNode<T> p) {
        if (p != null) {
            postorder(p.left);
            postorder(p.right);
            System.out.print(p);
        }
    }

    //层次遍历
    @Override
    public void levelorder() {
        if (this.root == null) return;
        Queue<BinaryNode<T>> binaryNodeQueue = new LinkedList<>();
        binaryNodeQueue.add(root);
        while (!binaryNodeQueue.isEmpty()) {
            BinaryNode<T> p = binaryNodeQueue.poll();
            System.out.print(p.data + "\t");
            if (p.left != null) {
                binaryNodeQueue.add(p.left);
            }
            if (p.right != null) {
                binaryNodeQueue.add(p.right);
            }
        }
        System.out.println();
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public int height() {
        return getHeight(root);
    }

    private int getHeight(BinaryNode<T> p) {
        if (p == null) return 0;
        return Math.max(getHeight(p.left) + 1, getHeight(p.right) + 1);
    }

    @Override
    public BinaryNode<T> search(T key) {
        return preSearch(root, key);
    }

    private BinaryNode<T> preSearch(BinaryNode<T> p, T key) {
        if (p.data == key) return p;
        BinaryNode<T> result = null;
        //进入左子树查询
        if (p.left != null) result = preSearch(p.left, key);

        if (result != null) return result; //避免结果被覆盖
        //进入右子树查询
        if (p.right != null) result = preSearch(p.right, key);

        return result;
    }

    public BinaryNode<T> parent(T key) {
        return preSearchParent(root, key);
    }

    private BinaryNode<T> preSearchParent(BinaryNode<T> p, T key) {
        if (p.left != null && p.left.data == key) return p;
        else if (p.right != null && p.right.data == key) return p;

        BinaryNode<T> result = null;
        if (p.left != null) result = preSearchParent(p.left, key);
        if (result != null) return result; //避免结果被覆盖
        if (p.right != null) result = preSearchParent(p.right, key);
        return result;
    }

    @Override
    public int level(T key) {
        return 0;
    }

    @Override
    public BinaryNode<T> remove(T key) {
        BinaryNode<T> result;
        if (key == root.data){      //判断是否是根节点
            result = this.root;
            this.root = null;
            return result;
        }
        BinaryNode<T> tBinaryNode = parent(key);
        if (tBinaryNode.left != null && tBinaryNode.left.data.equals(key)) {
            result = tBinaryNode.left;
            tBinaryNode.left = null;
        }
        else {
            result = tBinaryNode.right;
            tBinaryNode.right = null;
        }
        return result;
    }

    private int numberOfLeaves;

    public int countLeaves() {
        this.numberOfLeaves = 0;
        countLeaf(this.root);
        return numberOfLeaves;
    }

    private void countLeaf(BinaryNode<T> p) {
        if (p != null) {
            if (p.isLeaf()) numberOfLeaves++;
            countLeaf(p.left);
            countLeaf(p.right);
        }
    }
}
